package 经典问题;

import util.LogUtils;
import util.TraverseUtils;

/*
 * 回溯法：八皇后问题
 * @Date 2017-11-11 00：22
 * @TODO:尚未测试
 */
public class Eight_Queens {
	private static final int N = 8;
	private int mCount = 0;				//解發
	
	//初始化棋盘
	private int[][] initChess() {
		int[][] chess = new int[N][N];
		for (int i = 0; i < N; i ++) 
			for (int j = 0; j < N; j ++) 
				chess[i][j] = 0;
		return chess;
	}
	public void solution() {
		int[][] chess = initChess();
		putQueen2Chess(chess, 0);
	}
	
	private int[][] cloneNewChess(int[][] chess) {
		int[][] newChess = new int[N][N];
		for (int i = 0; i < N; i ++) {
			for (int j = 0; j < N; j ++) {
				newChess[i][j] = chess[i][j];
			}
		}
		return newChess;
	}
	private void putQueen2Chess(int[][] chess, int row) {
		if (row >= N) {
			printCurSolution(chess);
			return;
		}
		int[][] tChess = cloneNewChess(chess);
		int curRow = row;
	
		for (int col = 0; col < N; col ++) {
			if (isSafely(tChess, curRow, col)) {
				tChess[curRow][col] = 1;
				putQueen2Chess(tChess, ++row);
			}
		}
	}
	
	private void printCurSolution(int[][] tChess) {
		TraverseUtils.println("第"+(++mCount)+"種解法：", tChess);
	}
	
	/**
	 * 判断：中上、左上、右上是否安全
	 * @param tChess
	 * @param row
	 * @param col
	 * @return
	 */
	private static boolean isSafely(int[][] tChess, int row, int col) {
//		return false;
		for (int i=row-1; i>=0; i--) {
			if (tChess[i][col] == 1)return false;
		}
//		for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
//			if (tChess[i][j] == 1)	return false;
//		}
		for (int i=row-1, j=col+1; i>=0 && j<N; i--, j++) {
			if (tChess[i][j] == 1)	return false;
		}
		return true;     
	}
	
	public static void main(String[] args) {
		new Eight_Queens().solution();
	}
}
